package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class _20_ValidParentheses {
    public static void main(String[] args) {
        Solution solution = new _20_ValidParentheses().new Solution();
        boolean valid = solution.isValid("()");
        System.out.println(valid);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            Map<Character, Character> map = new HashMap<Character, Character>() {
                {
                    put(')', '(');
                }

                {
                    put(']', '[');
                }

                {
                    put('}', '{');
                }
            };
            Deque<Character> stk = new ArrayDeque<>();
            for (char c : s.toCharArray()) {
                if (!stk.isEmpty() && stk.peek().equals(map.get(c))) {
                    stk.pop();
                    continue;
                }
                stk.push(c);
            }
            return stk.isEmpty();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}